package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-03 16:03
 * @description: Functions of this class is
 *
 * 易理解题解（类似于数组的归并排序-空间复杂度O(1)）：
 * class Solution {
 *    class Solution {
 *     public ListNode sortList(ListNode head) {
 *         if (head == null || head.next == null)
 *             return head;
 *         ListNode fast = head.next, slow = head;
 *         while (fast != null && fast.next != null) {
     *             slow = slow.next;
 *             fast = fast.next.next;
 *         }
 *         ListNode tmp = slow.next;//！！！！搞清楚是slow.next而不是slow！！！！！！！！！将slow满指针所指的位置，作为每次二分链表的中间节点
 *         slow.next = null;//然后在这个中间位置的下一个指针赋值为null（用于二分的时候作为一个终止点）
 *         ListNode left = sortList(head);
 *         ListNode right = sortList(tmp);
 *         ListNode h = new ListNode(0);
 *         ListNode res = h;
 *         while (left != null && right != null) {
 *             if (left.val < right.val) {
 *                 h.next = left;
 *                 left = left.next;
 *             } else {
 *                 h.next = right;
 *                 right = right.next;
 *             }
 *             h = h.next;
 *         }
 *         h.next = left != null ? left : right;
 *         return res.next;
 *     }
 * }
 **/
public class NoNo排序链表 {
    public static void main(String args[]){

    }
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public static ListNode sortList(ListNode head) {
        int length = 0;
        ListNode p = head;
        while (p != null){
            length++;
            p = p.next;
        }
        int ans[]=new int[length];
        int k=0;
        while (head!=null){
            ans[k++]=head.val;
            head=head.next;
        }
        length=0;
        ListNode h=new ListNode();
        ListNode rear=h;
        ListNode x;
        Arrays.sort(ans);
        while (k-->0){
            x=new ListNode();
            x.val=ans[length++];
            x.next=null;
            rear.next=x;
            rear=x;
        }
        return h.next;
    }

}